The present invention relates generally to digital halftoning, and more particularly to a method of rendering a halftone image by utilizing a pixel-by-pixel comparison of an image against a stochastic dither matrix. The variation of dot patterns represented by the stochastic dither matrix is arranged by use of a filter-controlled force masking technique. The dot number and dot size are modulated to produce a uniform pattern and to break down the single pixel limit for blue noise masking.
Halftoning describes the process of displaying an image on a device that is capable of representing only a finite, discrete number of tone levels. Halftoning renders the illusion of various gray levels by using a binary pattern. Two examples in which halftoning is applied include the printing of an 8-bit image data on a 1-bit output device and the displaying of an 8-bit image data on a 4-bit monitor. Halftoning methods may be broken down into the present categories of neighborhood operations and point processing operations. Generally, neighborhood operations require considerably more computations than point processing operations. Examples of halftoning methods in the neighborhood operation category include: (1) the Model based error diffusion (MED) algorithm, as described in T. N. Pappas and D. L. Neuhoff, xe2x80x9cModel-based Halftoning,xe2x80x9d Proc. SPIE, vol. 1453, Human Vision, Visual Proc., and Digital Display III, San Jose, Calif., February 1992; (2) the least-square model-based (LSMB) algorithm, as described in T. N. Pappas and D. L. Neuhoff, xe2x80x9cLeast-squares Model-based Halftoning,xe2x80x9d Proc. SPIE, vol. 1666, Human Vision, Visual Proc., and Digital Display III, San Jose, Calif. February 1992; and (3) Model-based halftoning using direct binary search, as described in M. Analoui and J. P. Allebach, xe2x80x9cModel-based Halftoning Using Direct Binary Search,xe2x80x9d Proc. SPIE, vol. 1666, Human Vision, Visual Proc., and Digital Display III, San Jose, Calif. February 1992.
Screening is a point processing operation. In screening, a two dimensional image (to be reproduced) is compared pixel-by-pixel with an image-independent threshold matrix. Screening methods may be classified into AM (amplitude modulated) screening, and FM (frequency modulated) screening. In AM screening, dot size (amplitude) is varied according to gray level. Dot size increases with gray level while the dot number is fixed. In contrast, a set of fixed-size, fine dots are used in FM screening whereby the dots are variably spaced from neighboring dots. When the gray level increases, the dot number (frequency) increases and therefore dot spacing is denser. Because the dot size of FM screening is smaller than the dot size of AM screening, an original image can be rendered with a higher resolution by FM screening.
Clustered dot screening is a traditional AM screening method. It is being widely used in hard copy printings because it is robust to dot overlap and other printer distortions. In the screen pattern, the higher threshold dots are centered so that dots are clustered around the center. In other words, the printed pattern consists of a plurality of central black dots that increase in size and form macro-dots as the gray value of the neighborhood decreases. When ink dots are printed in clusters, most of the black dots overlap with other black dots rather than overlap with white spaces. Thus changes in the apparent gray level due to dot overlap are minimized, and the accuracy of the gray-scale rendition of the printed image is maintained to some extent. However, the macro-dots in clustered-dot screening (i.e., low-frequency periodic artifacts) are highly visible and unpleasant in appearance to the human eye. This ordered screening leads to fine image and detail loss and to a moirxc3xa9 pattern when a prescreened image or color image is rendered.
In Bayer""s dispersed-dot screening (which is a conventional FM screening method), the threshold matrix is designed to maximize the distance between printed dots in the printed image so that a number of dispersed micro-dots scattered throughout the pattern are produced. Since the conventional Bayer""s threshold matrices are approximately based on regular orderings of the threshold values, visible patterns, such as textural contouring, often appear in the output images.
To overcome these drawbacks of ordered dispersed-dot screening, randomness is intentionally added to the dot pattern. In previous known approaches, there are two ways to obtain a visually favored pattern. One way is to optimize a random pattern by use of blue noise screening, as discussed in M. Yao and K. J. Parker, xe2x80x9cModified Approach to the Construction of a Blue Noise Mask,xe2x80x9d Journal of Electronic Imaging, vol. 3(1), January 1994, pp. 92-97; U.S. Pat. No. 5,111,310 to Parker; U.S. Pat. No. 5,535,020 to Ulichney; U.S. Pat. No. 5,317,418 to Lin; U.S. Pat. No. 5,463,720 to Granger; U.S. Pat. No. 5,557,709 to Shu; U.S. Pat. No. 5,673,121 to Wang; U.S. Pat. No. 5,557,602 to Cooper et al., and U.S. Pat. No. 5,745,660 to Kolpatzik et al. Starting from a random pattern, the above approaches use a dot profile, find voids and cluster xe2x80x9cclumpsxe2x80x9d, swap clumps and uniformly redistribute xe2x80x9cONxe2x80x9d and xe2x80x9cOFFxe2x80x9d dots. Clumps are defined as unwanted low-frequency structures in blue noise mask construction.
The other way to obtain a visually favored pattern is to adjust a regular pattern to be random in some extent. In W. Purgathofer et al., xe2x80x9cImproved Threshold Matrices for Ordered Dithering,xe2x80x9d Graphics Gems V, pp. 297-301, Academic Press, Inc. (1995), an approach is discussed whereby a repulsive force field generated by all xe2x80x9cONxe2x80x9d dots is used to influence the resulting dot distribution.
The above-mentioned approaches for modifying ordered dispersed-dot screening avoid the contouring artifacts of Bayer""s dithering, provide more detail and smooth image rendering, and eliminate moirxc3xa9 pattern in clustered-dot screening. However, in the above approaches, the image highlight areas can suffer from the visibility of individually printed dots. Therefore, images that are reproduced appear more grainy or noisy than those images produced in the light tone portion by clustered-dot screening.
Moreover, the above stochastic screening methods are only preferably selected when a display device can accommodate a single pixel. The reason is that when a single pixel can not be produced, it simply may be replicated to improve printability but resolution is sacrificed and the image appears more grainy.
In a laser printing (electrophotography) process, a photosensitive drum is charged with a scanning illumination, leaving a latent image to attract opposite-charged toner particles. The toner image is then offset to paper.
There are two additional problems for dot pattern reproduction when previous known stochastic screening methods are used in electrophotography. First, toners with the same charge repulse each other. Since the charge force is not uniform, some single dots or microdots aggregate. Again, the image looks more noisy. Second, dot misregistration results in more significant color shifts in a color image than in images reproduced by clustered-dot screening.
In U.S. Pat. No. 5,740,279 to Wang et al., it is indicated that conventional blue noise screening may work well in ink-j et printing but not in electrophotography. Thus, Wang discloses a composite lookup table (LUT) merged by a cluster screen and a stochastic screen. However, Wang does not guarantee the blue noise characteristic of a dot pattern at each gray level because the two processes are separated.
Therefore, there is a need for a stochastic screening method that is capable of producing a smooth and high detailed image that is free of a moirxc3xa9 pattern. There is also a need for a method for controlling the variation of patterns from a regular structure to a random structure so as to obtain a desirable mask. There is a further need for an approach that considers the physical behavior of a printer (e.g., dot overlap, dot reproduction, and dot registration) when generating a dithered mask.
In one aspect of the present invention, a dither matrix (mask) is generated for rendering a halftone image. The dither matrix forms a pattern upon completion. The method for forming the dither matrix includes the steps of modulating, at a each gray level, the dot number in the pattern for forming the dither matrix, and modulating, at each gray level, the dot size in the pattern for forming the dither matrix.
The present invention eliminates moirxc3xa9 patterns and also minimizes the grainyimage problem in previous known stochastic screening methods by controlling the variation of the pattern regularity of the mask. A filter-controlled force is used for generating the stochastic dither matrix. Modulation of dot size (amplitude) and dot number (frequency) is performed integrally at each gray level during generation of the mask. By integrating frequency modulation (FM) and amplitude modulation (AM) in the generation of the mask, it is possible to break down the limit of single pixel printability of previous known stochastic screening methods. This integration of AM and FM modulation is in contrast to conventional approaches which teach only dot number modulation for blue noise screening. A halftone image is then rendered by utilizing a pixel-by-pixel comparison of an image against the generated stochastic dither matrix. The invention permits a mid-size mask (such as a 128xc3x97128 mask) to be applied effectively in 1200 dpi laser printing.